\documentclass[paper=a4, fontsize=11pt]{scrartcl}
\usepackage{charter} 
\usepackage{amsmath}
\usepackage[top=0.75in, bottom=1in, left=0.5in, right=0.5in]{geometry} 
\newcommand{\bfvec}[1]{\mbox{\boldmath$#1$}}
\title{	
\normalfont \normalsize 
\textsc{Shanghai Jiaotong University, Zhiyuan College} \\ [25pt]
\huge Exercises for Chapter 2 \\
}
\author{Feng Shi}
\date{\normalsize\today}
\begin{document}
\maketitle

\newpage

\section{Exercise 2.1}
Solution:

$$\frac{1}{2}, \frac{1}{3}, 0, \frac{1}{4}, \frac{1}{6}$$
\section{Exercise 2.2}
\section{Exercise 2.3}
\section{Exercise 2.4}
Solution:

Consider this in d-dimension.

Let $\bfvec{x_{1}}$ and $\bfvec{x_{2}}$ be the two random vectors.

Choose one of the vector, say $\bfvec{x_{1}}$, and rotate it to be the north pole.

If the angle between the two vectors is less than 45, then $\bfvec{x_{2}}$ should be
within a cone of 45$^{\circ}$ whose axis is $\bfvec{x_{1}}$. Then it is neccessary 
that it is within 45$^{\circ}$ from $\bfvec{x_{1}}$ in every dimension, that is, 
it must be within a square cone of 45$^{\circ}$ in every direction from $\bfvec{x_{1}}$. 

Since $\bfvec{x_{1}}$ and $\bfvec{x_{2}}$ are both $0-1$ vectors, the above situation
requires $x_{1}(i)=x_{2}(i)$ in each direction. The probability of $x_{2}$ be within
the square cone is $\frac{1}{2^{d}}$. Thus in high dimension the angle between the
two random vectors being less than 45 is almost zero.

\section{Exercise 2.5}
Solution:

When $d=2$, let the line through the center be $x-axis$,
let
	$$S_{2}(x_{0}) = 2 \int_{0}^{x_{0}} \sqrt{1+{(\frac{-x}{\sqrt{2-x^{2}}})}^{2}}
		=2\sqrt{2} arcsin(x_{0})$$
	$$S'_{2}(x_{0})=\frac{2 \sqrt{2}}{\sqrt{1-x_{0}^{2}}}$$
	$S'_{2}(x)$ is the projected surface area on the line.

	\vspace{6pt} 

When $d=3$, let the line through the center be $x-axis$,
let 
	$$S_{3}(x_{0}) = \int_{0}^{x_{0}} 2\pi f(x) \sqrt{1+f'(x)^{2}}dx$$
	where $f(x)$ is the 3-dimensional sphere $f(x)=\sqrt{3-x^{2}}$.
	$$S_{3}(x_{0}) = \int_{0}^{x_{0}} 2\pi \sqrt{3-x^{2}} \sqrt{1+\frac{x^{2}}{3-x^{2}}} dx 
		= \int_{0}^{x_{0}} 2\sqrt{3}\pi dx$$
	So the projected surface area is always $2\sqrt{3}\pi$ along the line.

	\vspace{6pt}

When d is large, use the following approach to get an approximation of the surface area 
of the sphere of radius $\sqrt{d}$ when $d$ is large:
randomly generate points with each coordinate according to Gaussian with unit variance.
As said in Chapter 2.5, those randomly generated points will lie in a thin annulus of width $O(1)$
at radius $\sqrt{d}$. So this annulus can be an approximation of the surface area 
of the sphere of radius $\sqrt{d}$ when $d$ is large.

As each coordinate of the points we generate is Gaussian, 
we will get a unit variance Gaussian if we
project the annulus onto any one axis through the origin.
So we will get a unit variance Gaussian if we project the surface area 
of the sphere of radius $\sqrt{d}$
onto a line through the center when $d$ is large.
So for large $d$ the projected surface area should
 behave like a Gaussian.

\section{Exercise 2.6}
\section{Exercise 2.7}
Solution:

1.	Because each coordinate of $x$ has mean 0,
the mean of $x$ is the origin.

2.	$$\sigma(x_{i})=E(x_{i}^{2})-E(x_{i})^{2}=E(x_{i}^{2})=\frac{1}{d}E(|x|^2)$$
	$$E(|x|^2)=\frac{1}{V(d)}\int_{0}^{1}A(d)r^{d-1}r^{2}=\frac{d}{d-2}$$
	$$\sigma(x)=\frac{1}{d}E(|x|^2)=\frac{1}{d-2}$$

3.	$$E(x_{i}^{2})=\sigma(x_{i})=\frac{1}{d-2}$$
	$$\sum_{i=1}^{d}u_{i}^{2}E(x_{i})^2=\sum_{i=1}^{d}\frac{u_{i}^2}{d-2}$$

4.	The volume of the intersection is twice the volume of section:
	$${\bfvec{x}:|\bfvec{x}|\leq 1,x_{1}\geq \frac{a}{2}}$$
	which can be calculated by integral:
	$$\int_{0}^{\sqrt{1-\frac{a^{2}}{4}}} A(d)r^{d-1}dr$$
	with Bernoulli inequality $(1+x)^{a}\geq 1+ax$, $1+x\leq e^{x}$ and
	$A(d)=dV(d)$, the upper bound can be proved.

5.	Just substitute $a=\frac{r}{\sqrt{d}}$ directly yields the conclusion.

6.	The expected radius of the spherical Gaussian is $\sigma\sqrt{d}$
	where $\sigma$ is standard deviation. 
	
	$\quad$Its projection on and axis is also Gaussian with standard deviation $\sigma$.
	
	$\quad$The shared mass is given by integrating over $x_{1}-axis$:
	
	$$\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi} \sigma} min\Big(e^{-\frac{x_{1}^{2}}{2}},e^{-\frac{(1-x_{1})^{2}}{2}}\Big)dx_{1}$$
	$\quad$which can be bounded by:

	\begin{align*}
	\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi} \sigma}
		min\Big(e^{-\frac{x_{1}^{2}}{2}},e^{-\frac{(1-x_{1})^{2}}{2}}\Big)dx_{1} 
		&\leq \int_{-\infty}^{\frac{a}{2}} + \int_{\frac{a}{2}}^{\infty} \\
		&\leq \int_{\frac{a}{2}}^{\infty} \\
		&\leq \int_{\frac{a}{2}}^{\infty} \frac{2x}{a} \\
		&\leq \frac{2}{a}e^{-\frac{a^{2}}{8\sigma}}
	\end{align*}
	
$\quad$So the shared mass drops exponentially.

\section{Exercise 2.8}
Solution:

Mutilply $e^{-x^{2}}$ with $\frac{x}{a}$ and it is integrable.

When $\alpha>3\sigma$ this is a good bound.
\section{Exercise 2.9}
\section{Exercise 2.10}

Solution:

\begin{displaymath}
	V(d) = \frac{d}{2} \frac{\pi ^ {\frac{d}{2}} }{\Gamma( \frac{d}{2})}
	= \frac{\pi ^ {\frac{d}{2}}}{\Gamma(1 + \frac{d}{2})}
	= \left\{ \begin{array}{ll}
			\frac{\pi^{\frac{d}{2}}}{(d/2)!} & \textrm{if $d$ is even}\\
			\frac{ \pi ^ {\lfloor d/2 \rfloor} 2 ^ {\lceil d/2 \rceil}}{d!!} & \textrm{if $d$ is odd}
	\end{array} \right.
\end{displaymath}

so we have the recursion:

$V(0) = 1$

$V(1) = 2\pi$

$V(d) = \frac{2\pi}{d} V(d-2)$ for $d>1$

so we can calculate:
\begin{align*}
	V(0)&= (1/0!)\pi^{0}=1\\
	V(1) &= (2^{1}/1!!)\pi^{0}=2\\
	V(2) &= (1/1!)\pi^{1}=\pi\\
	V(3) &= (2^{2}/3!!)\pi^{1}=\frac{4}{3}\pi\\
	V(4) &= (1/2!)\pi^{2}=\frac{1}{2}\pi^{2}\\
	V(5) &= (2^{3}/5!!)\pi^{2}=\frac{8}{15}\pi^{2}\\
	V(6) &= (1/3!)\pi^{3}=\frac{1}{6}\pi^{3}\\
\end{align*}
for $d>6$, $\frac{2\pi}{d}<1$, so the volumes will be decreasing.
Thus we can see when $d=5$, the volume of d-dimensional unit sphere is maximum.

\section{Exercise 2.11}

Solution:

The volume of a d-dimensional sphere with a constant radius r independent of d is
	$r^{d}V(d)$, where $V(d)$ stands for the volume of a unit-radius d-dimensional sphere.
	
	Assume $d$ is even and use Stirling's approximation for $\Gamma(\frac{d}{2})$ :
	\begin{displaymath}
		\Gamma(1+\frac{d}{2}) = (\frac{d}{2})! \sim (\frac{d}{2e})^{\frac{d}{2}} \sqrt{\pi d}
	\end{displaymath}
	So the volume is
	$$V_{d}(r) = \frac{\pi^{\frac{d}{2}} r^{d}}{(\frac{d}{2e})^\frac{d}{2} \sqrt{\pi d}}$$
	as assumed is a constant. Setting $V_{d}(r)=c$, yields
	\begin{align*}
		r&=\sqrt[d]{\frac{cd\Gamma(\frac{d}{2})}{2}}\\
		&=\sqrt[d]{c(\frac{d}{2\pi e})^{\frac{d}{2}}\sqrt{d\pi}}
	\end{align*}
	When $r=\sqrt{\frac{2\pi e}{d}}$, $V_d(r)$ is constant.

\section{Exercise 2.12}
\section{Exercise 2.13}
\section{Exercise 2.14}
\section{Exercise 2.15}

Solution:
	
	Fix $x_{1}=1$ on $x_{1}-axis$ the north pole, the volume of the cylinder entirely fixed 
	in the upper hemisphere has height $x_{1}$, surface area of the volume of a $(d-1)$-dimensional
	sphere with radius $\sqrt{1-x_{1}^{2}}$, that yields the volume of the cylinder :
	$$V_{d}(x_{1}) = V(d-1) (1-x_{1}^{2})^{\frac{d-1}{2}} x_{1}$$
	where V(d-1) is a constant. Let $f(x) = (1-x^{2})^\frac{d-1}{2} x$.

	$V_{d}(x_{1})$ has maximium value when $x_{1} = \sqrt{\frac{1}{d}}$, this comes from setting
	the derivative of $f(x)$ equal to 0 :
	$$f'(x) = (1-x^{2})^\frac{d-1}{2} - (d-1) x^{2} (1-x^{2})^\frac{d-3}{2}=0$$
	which implies $x_{1} = \sqrt{\frac{1}{d}}$ .

\section{Exercise 2.16}
Solution:

$$V_{c}{d}=V(d-1)r^{d-1}h$$
\section{Exercise 2.17}
\section{Exercise 2.18}
\section{Exercise 2.19}
\section{Exercise 2.20}
\section{Exercise 2.21}
\section{Exercise 2.22}
Solution:

A unit variance Gaussian.
$$\Bigg( Why?\Bigg)$$
\section{Exercise 2.23}
\section{Exercise 2.24}
\section{Exercise 2.25}
\section{Exercise 2.26}
Solution:

The projected surface area of a d-dimensional sphere of $\sqrt{d}$ radius onto a line throgh the origin
is a Gaussian of unit variance when d is large.

As Gaussian with standard deviation $\sigma$ has $99.7\%$ of the probability between $2*3\sigma$ about the mean, 
we can assume a band of width 6 containing most of the surface area for the unit variance Gaussian.

So the largest distance between the two hyperplanes is about $\frac{6}{\sqrt{d}}$
\section{Exercise 2.27}
Solution:

If the vector is to be within a cone of 45$^{\circ}$, the vetor must be within
45$^{\circ}$ in every direction.
Thus the vector must be within a square cone containing entirely the cone.
The probability in given dimension a random vector is 45$^{\circ}$ to the north in one
direction is $\frac{1}{2}$, so the probability that the vector is within the
spuare cone is $(\frac{1}{2})^{d}$, which goes to zero as d approaches infinity.
And since the cone is completely contained in the square cone, the probability
that the angle between two random vectors is at most 45$^{\circ}$ goes to zero.

The volume of the cone is $$V_c{d}=\int_{0}^{\frac{\sqrt{2}}{2}} A(d)r^{d-1}dr$$
and $A(d)=dV(d)$, so
$$V_c{d}=dV(d)\int_{0}^{\frac{\sqrt{2}}{2}} r^{d-1}dr$$
The ratio of the cone to the hemisphere is
$$\frac{V_c{d}}{V(d)}=d\int_{0}^{\frac{\sqrt{2}}{2}} r^{d-1}dr$$

\section{Exercise 2.28}
Solution:

Projecting a vector $\bfvec{x}$ in d-space to the line from $(0,0,...,0)$ to $(1,1,...,1)$ is equivalent to
taking dot product with a unit vecort $\bfvec{e}=(\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}},...,\frac{1}{\sqrt{d}})$.

By Central Limit Theorem, $\bfvec{x} \cdot \bfvec{e}-\mu=\frac{1}{\sqrt{d}}(x_{1}+x_{2}+...+x_{d}-d\mu)$
where $\mu$ is the mean of the dot product, converges to Gaussian with mean 0 and variance $\sigma^{2}$ same as
 the variance of the dot product.

 By symmetric property we see the mean of dot product is $\frac{1}{2}$. The variance of the dot product is given by:
 $$\sigma^{2}=\frac{\sum_{i=1}^{d}{  (x_{i}-\frac{1}{2})^{2}  }}{d}$$
 which is $O(1)$. So the "density" of projected points is like a Gaussian with variance $O(1)$ and center of mid-point
 of the line.

\section{Exercise 2.29}

\begin{enumerate}

\item[-]
{\Large \textbf{Solution 1:}}
\begin{enumerate}
\item[1.]
The surface area of a $d-$dimensional unit cube is the sum of surface areas of its 
sides, which are $(d-1)-$dimensional volumes. And the $d-$dimensional cube has $2d$
sides. So a $d-$dimensional unit cube has surface area of $2d$.

\item[2.]
Consider generating uniformly random points on the surface of the $d-$dimensional cube
and calculate the probability of the points lying near the equator defined above. What
I want to prove is that the distance from the random points to the hyperplane is
almost zero.

Since a $d-$dimensional cube has $2d$ sides of $(d-1)-$dimension,
a randomly chosen point on the surface of the $d-$dimensional cube has a probablity
of $\frac{1}{2d}$ lying on the side 
$$\lbrace(x_{1},x_{2},...,x_{i}=0,...,x_{d}) | 0\leq x_{j}\leq 1,j\in[1,d]\backslash i\rbrace$$
Consider generating uniformly random points on this side. This is just generating
each coordinate randomly on $[0,1]$ since it's a $(d-1)-$dimensional cube. 
So each coordinate has an expectation of $\frac{1}{2}$ and the expectation of the
sum of every coordinate is $\frac{d-1}{2}$ by linearity of expectation (and each
coordinate is independent of course).

By symmetry there is a side
$$\lbrace(x_{1},x_{2},...,x_{i}=1,...,x_{d}) | 0\leq x_{j}\leq 1,j\in[1,d]\backslash i\rbrace$$
and the expectation of sum of the coordinates of a randomly generated points on 
this surface is $\frac{d+1}{2}$. This yields an expectation of sum of coordinates on
a pair of sides of $\frac{d}{2}$.
Let random variable $\bfvec{X}$ denote $\sum_{i=1}^{d}x_{i}$
So the expectation of sum of coordinates of a point on the surface 
of a $d-$dimensional unit cube is 
$$E(\bfvec{X})=E(\sum_{i=1}^{d}x_{i})=\frac{d}{2}\quad \mbox{$\bfvec{x}$ is on the surface}$$ 
To calculate the variance, change the coordinate system and make origin the center of the cube,
then each coordinate has range $[-\frac{1}{2},\frac{1}{2}]$.
Changing the coordinate system (i.e. changing the expected value) won't change the variance.
Denote the cube with $C^{d}$.
\begin{align*}
	\sigma(\bfvec{X})&=\int_{C^{d}}(\bfvec{X}-\frac{d}{2})^2 dS \\
					&=\int_{C^{d}}(\sum_{i=1}^{d}x_{i}^{2}+
					\sum_{i=1}^{d}\sum_{j=1,i\neq j}^{d}x_{i}x_{j})dS \\
\end{align*}
Since
$$\int_{-\frac{1}{2}}^{\frac{1}{2}}x_{i}x_{j}dx_{i}=0 \quad \textrm{$i\neq j$}$$

\begin{align*}
	\sigma{\bfvec{X}}&=\int_{C^{d}}\sum_{i=1}^{d}x_{i}^{2}dx_{i} \\
					&=d\int_{C^{d}}x_{i}^{2}dx_{i} \\
					&=d\int_{-\frac{1}{2}}^{\frac{1}{2}}\int_{-\frac{1}{2}}^{\frac{1}{2}}...
					\int_{-\frac{1}{2}}^{\frac{1}{2}}x_{i}^{2}dx_{1}dx_{2}...dx_{d} \\
					&=\frac{d}{12}
\end{align*}
According to Chebyshev's inequality
$$p(|\bfvec{X}-\frac{d}{2}|\geq\epsilon)\leq\frac{\frac{d}{12}}{\epsilon^2}
=\frac{d}{12\epsilon^{2}}$$
Now we denote the axis through the center of the cube and perpendicular to the equator
the $o-axis$, and we take the ``thickness'' of the equatorial slice half of the length
of the $o-axis$, namely $\sqrt{d}$, and prove that the probablity of the 
randomly generated point lying outside the slice goes to zero as $d\to\infty$.
(in the below we prove in half of the cube "above" the equator)

Denote a randomly generator point $\bfvec{x}$, the hyperplane parrallel to the
equator and with $\bfvec{x}$ on it $\Pi$. Then when the distance between the equator 
and $\Pi$ is $\frac{\sqrt{d}}{2}$, the distance of $\bfvec{x}$ from the equator is
actually $$\Delta d=\frac{|\bfvec{x}\cdot\bfvec{n}|}{|\bfvec{n}|}=\frac{|X-\frac{d}{2}|}{\sqrt{d}}$$
$$|\bfvec{X}-\frac{d}{2}|=\sqrt{d} \Delta d $$
$$\sigma(\Delta d)=\frac{\sigma(\bfvec{X})}{(\sqrt{d})^2}=\frac{1}{12}$$
That says, when $\bfvec{X}$ is $\epsilon$ from its expected value $\frac{d}{2}$, the
distance between the two hyperspaces is actually $\frac{\epsilon}{\sqrt{d}}$.
Let $\epsilon=c\frac{d}{2}$, then
$$p(|\bfvec{X}-\frac{d}{2}|\geq c\frac{d}{2})\leq\frac{1}{c^2d}$$
also
$$p(|\Delta d|>c\sqrt{d})\leq \frac{1}{c\sqrt{d}}$$
where c could be very small for the "equatorial slice" to be thin 
with respect to the length of $o-aixs$.
We can conclude that, when d is large, most of the points
generated randomly lie near the equator given by
$$\lbrace \bfvec{x}:\sum_{i=1}^{d}x_{i}=\frac{d}{2} \rbrace$$
So the surface area is near the equator(with respect to a porpotion to the length of
the axis).
\end{enumerate}
\vspace{10pt}

\item[-]
{\Large \textbf{Solution 2:}}(not very rigorous)
\begin{enumerate}
\item[1.]
same as solution 1.
\item[2.]
{\large \textbf{Proposition 1.}} When $d$ is large, an axis is almost contained in the
equator given by $\lbrace \bfvec{x}:\sum_{i=1}^{d}x_{i}=\frac{d}{2} \rbrace$ in a 
$d-$dimensional cube. Actually every axis is almost contained in the equator.

{\large \textbf{Proposition 2.}} The surface area of a $(d-1)-$dimensional side of a
$d-$dimensional cube is the volume of a $(d-1)-$dimensional cube.

{\large \textbf{Proposition 3.}} A $(d-2)-$dimensional "line" connecting two $(d-1)-$-
dimensional sides int a $d-$dimensional cube is an axis of the cube, and an equator
of a $(d-1)-$dimensional cube.
(These propositions won't be proved so this proof is not rigorous)

Given the above propositions, we only need to prove that the volume of a high
dimensional cube is concentrated at its equator.

Move the cube with its center at the origin. Each coordinate havs range
$[-\frac{1}{2},\frac{1}{2}]$. Let $C^{d}$ denote the cube. Set
$$S_{d}(\bfvec{x})=\sum_{i=1}^{d}x_{i}$$
and define the "equatorial slice" according to the question
$$S_{\epsilon}=\lbrace \bfvec{x}\in C^{d} | |\frac{S_{d}(\bfvec{x})}{d}|<\epsilon \rbrace$$
by the Weak Law of Large Numbers, we have
$$\lim_{d \to \infty} Volume(S_{\epsilon})=0$$
We notice
$$(S_{d}(\bfvec{x}))^2=\sum_{i=1}^{d}x_{i}^{2}+\sum_{i=1}^{d}\sum_{j=1,j\neq i}^{d}2x_{i}x_{j}$$
When we integrate over $C^{d}$, since
$$\int_{-\frac{1}{2}}^{\frac{1}{2}}x_{i}dx_{i}=0$$
and
$$\int_{C^{d}}x_{i}^{2}dx_{i}=\int_{-\frac{1}{2}}^{\frac{1}{1}} \int_{-\frac{1}{2}}^{\frac{1}{1}}... \int_{-\frac{1}{2}}^{\frac{1}{1}} x_{i}^{2}dx_{i}dx_{2}...dx_{d}=\frac{1}{12}$$
So $$\sigma^{2}=\frac{d}{12}$$ (this can be used to complete the proof in solution 1)

Applying Chebyshev's inequality yields
$$Volume({\bfvec{x}||S_{d}(\bfvec{x})|>\delta})<\frac{d}{12\delta^2}$$
$$Volume({\bfvec{x}||\frac{S_{d}(\bfvec{x})}{d}|>\epsilon})<\frac{1}{12n\epsilon^2}$$
which means that the volume of a $d-$dimensional cube is concentrated around the
equator. Thus by propositions above we have the surface area around the equator too.
(not very rigorous)

\end{enumerate}
\vspace{10pt}

\item[-]
{\Large \textbf{Solution 3:}}(not very rigorous)
\begin{enumerate}
\item[1.]
same as solution 1.
\item[2.]
The shape of the intersection of the equator and the $d-$dimensional cube is a 
hexagon when $d=3$, and it's a octahedron (projected to 3-dimension) when $d=4$.
As $d$ increases the number of the sides of the intersection area increase. 
When $d\to\infty$, the area becomes a $(d-1)-$dimensional sphere. 

We take $\epsilon$ and prove that ratio of a upper bound of the surface area beyond 
distance $\epsilon$ from the equator over half of the surface area of the unit cube 
goes to zero as $d\to\infty$.

The equatorial slice becomes a sphere when $d\to\infty$ and integrating the volume 
yeilds:
\begin{align*}
	Area(S)&=\int_{\epsilon}^{1} (1-x_{1})^\frac{d-2}{2}\frac{1}{\sqrt{(1-x_{1}^{2})}}
A(d-1)dx_{1}\\
&=A(d-1)\int_{\epsilon}^{1} (1-x_{1})^\frac{d-3}{2}\\
&\leq A(d-1)\int_{\epsilon}^{\infty} e^{-\frac{d-3}{2}x_{1}^2}\\
&\leq A(d-1)\int_{\epsilon}^{\infty} \frac{x_{1}}{\epsilon}e^{-\frac{d-3}{2}x_{1}^2}dx_{1}\\
&\leq \frac{1}{\epsilon(d-3)}e^{-\frac{d-3}{2}\epsilon^{2}}A(d-1)\\
\end{align*}
The surface area of half of the unit cube is $d$, so the ratio is:
$$\frac{Area(x)}{\frac{1}{2}A_{c}(d)}
\leq \frac{1}{\epsilon d(d-1)}e^{-\frac{d-3}{2}\epsilon^{2}}A(d-1)$$
which clearly goes to zero as $d\to\infty$. So the surface area of a unit cube is
concentrated close to the equator.
\end{enumerate}

\vspace{10pt}


\end{enumerate}

\section{Exercise 2.30}
\section{Exercise 2.31}
\section{Exercise 2.32}
\section{Exercise 2.33}
\section{Exercise 2.34}
\section{Exercise 2.35}
\section{Exercise 2.36}
Solution:

1.	$$P(x_{i}^4\leq\frac{1}{2})=(\frac{1}{2})^\frac{1}{4}$$
	$$P(\sum_{i=1}^{d}{x_{i}^4}\leq\frac{1}{2})=((\frac{1}{2})^\frac{1}{4})^{d}=\frac{1}{2^{d/4}}$$

2.	

3.	Let $Vol(d)$ be the volume of K in d-space. 
\begin{align*}
Volume(K\cap { \bfvec{x}|x_{1}\geq \alpha})&=\int_{\alpha}^{1}
{Volume((x_{2},x_{3},...,x_{d})|x_{2}^{4}+x_{3}^{4}+...+x_{d}^{4}\leq 1-t^{4})}dt\\
&=\int_{\alpha}^{1}{Vol(d-1)(1-t^{4})^\frac{d-1}{4}}dt\\
&\leq Vol(d-1)\int_{\alpha}^{1}{\frac{t^{3}}{\alpha^{3}}(1-t^{4})^\frac{d-1}{4}}dt\\
\end{align*}
	Above is an upper bound on the volume of $K$ beyond $x_{1}=\alpha$. 
	Next we get an lower bound on the volume of K within that limitation:
	$$\int_{0}^{1}{Vol(d-1)(1-t^{4})^\frac{d-1}{4}}dt 
	\geq Vol(d-1)\int_{0}^{\frac{1}{\sqrt[4]{d}}}{(1-t^{4})^\frac{d-1}{4}}dt
	\geq$$ 
\section{Exercise 2.37}
\section{Exercise 2.38}
\section{Exercise 2.39}
\section{Exercise 2.40}
\section{Exercise 2.41}
\section{Exercise 2.42}
\section{Exercise 2.43}
\section{Exercise 2.44}
Solution:

1.	Brute force! Computing all $n^{3}$ pairwise distance each with $n$ coordinates takes $O(n^{3})$ time.

2.	Project the two sets $P,Q$ to a randomly selected $O(lnn)$ dimensional space.
	The projection preserves pairwise distance and strictly preserves distance 0.
	Then compute all pairwise distance.
\section{Exercise 2.45}
\section{Exercise 2.46}
\section{Exercise 2.47}
will not do this
\section{Exercise 2.48}
will not do this
\end{document}

